// 版权所有2011 Go作者。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ir

// 强连接组件。
// 
// 在相互递归函数的最小集合上运行分析
// 或单个非递归函数，自下而上。
// 
// 查找这些集合就是在静态调用图中按逆拓扑顺序查找强连通组件
// 。
// 算法（称为Tarjan算法）取自
// Sedgewick，算法，第二版，第482页，有两个修改。
// 
// 首先，隐藏闭包函数（n.Func.ishidnClosure（））不能是已连接组件的根。拒绝将其用作根
// 会迫使它进入其出现的函数的组件中。
// 这对逃逸分析更方便。
// 
// 第二，每个函数成为图中的两个虚拟节点，
// 带有数字n和n+1。我们将函数的节点号记录为n 
// 但从节点n+1进行搜索。如果搜索告诉我们组件
// number（min）是n+1，我们知道这是一个微不足道的组件：一个函数
// 加上它的闭包。如果搜索告诉我们组件编号是
// n，那么就有一条从节点n+1返回节点n的路径，这意味着
// 函数集是相互递归的。当分析单个非递归函数时，逃逸分析可能比分析一组相互递归的函数时更精确。

type bottomUpVisitor struct {
	analyze  func([]*Func, bool)
	visitgen uint32
	nodeID   map[*Func]uint32
	stack    []*Func
}

// VisitFuncsBottomUp调用列表中列出的ODCLFUNC节点上的分析。
// 它使用连续的函数组调用analyze，从调用图底部向上运行。每次使用
// 函数列表调用analyze时，该列表中的每个函数只调用列表中的其他函数
// 或在之前调用
// analyze时传递的函数。闭包与其外部函数出现在同一列表中。
// 列表尽可能简短，同时保留这些要求。
// （在一个典型的程序中，许多对analyze的调用将仅通过单个函数传递。）传递用于分析
// 的布尔参数'recursive'指定列表中的函数是否相互递归。
// 如果recursive为false，则列表只包含一个函数及其闭包。
// 如果recursive为true，则列表可能仍然只包含一个函数，如果该函数本身是递归的，则列表可能仍然只包含一个函数。
func VisitFuncsBottomUp(list []Node, analyze func(list []*Func, recursive bool)) {
	var v bottomUpVisitor
	v.analyze = analyze
	v.nodeID = make(map[*Func]uint32)
	for _, n := range list {
		if n.Op() == ODCLFUNC {
			n := n.(*Func)
			if !n.IsHiddenClosure() {
				v.visit(n)
			}
		}
	}
}

func (v *bottomUpVisitor) visit(n *Func) uint32 {
	if id := v.nodeID[n]; id > 0 {
		// 已访问
		return id
	}

	v.visitgen++
	id := v.visitgen
	v.nodeID[n] = id
	v.visitgen++
	min := v.visitgen
	v.stack = append(v.stack, n)

	do := func(defn Node) {
		if defn != nil {
			if m := v.visit(defn.(*Func)); m < min {
				min = m
			}
		}
	}

	Visit(n, func(n Node) {
		switch n.Op() {
		case ONAME:
			if n := n.(*Name); n.Class == PFUNC {
				do(n.Defn)
			}
		case ODOTMETH, OMETHVALUE, OMETHEXPR:
			if fn := MethodExprName(n); fn != nil {
				do(fn.Defn)
			}
		case OCLOSURE:
			n := n.(*ClosureExpr)
			do(n.Func)
		}
	})

	if (min == id || min == id+1) && !n.IsHiddenClosure() {
		// 此节点是强连接组件的根。

		// 传递给VisitDelist的原始最小值是v.nodeID[n]+1。
		// 如果visitcolist返回到v.nodeID[n]，那么这个
		// 块是一组相互递归的函数。
		// 否则它只是一个不会递归的单独函数。
		recursive := min == id

		// 从堆栈中删除连接的组件。
		// 标记walkgen，以便将来的访问返回大量
		// 以免影响调用方的最小值。

		var i int
		for i = len(v.stack) - 1; i >= 0; i-- {
			x := v.stack[i]
			v.nodeID[x] = ^uint32(0)
			if x == n {
				break
			}
		}
		block := v.stack[i:]
		// 对这组函数运行转义分析。
		v.stack = v.stack[:i]
		v.analyze(block, recursive)
	}

	return min
}
